#define  _CRT_SECURE_NO_WARNINGS


class Solution {
public:
    int maximumSafenessFactor(vector<vector<int>>& grid) {
        int n = grid.size();
        int d[n][n];
        memset(d, -1, sizeof(d));
        queue<pair<int, int>> q;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (grid[i][j] == 1)
                {
                    d[i][j] = 0;
                    q.push({ i, j });
                }
        int dx[4] = { 0, 0, 1, -1 };
        int dy[4] = { 1, -1, 0, 0 };
        while (!q.empty())
        {
            auto top = q.front();
            q.pop();
            for (int k = 0; k < 4; k++)
            {
                int x = dx[k] + top.first;
                int y = dy[k] + top.second;
                if (x < 0 || x >= n || y < 0 || y >= n || d[x][y] != -1)
                    continue;
                d[x][y] = d[top.first][top.second] + 1;
                q.push({ x, y });
            }
        }

        int vis[n][n];
        memset(vis, -1, sizeof vis);
        int left = 0, right = 2 * (n - 1);
        while (left < right)
        {
            int mid = left + (right - left + 1) / 2;
            queue<pair<int, int>> q;
            if (d[0][0] >= mid)
                q.push({ 0, 0 });

            while (!q.empty())
            {
                auto top = q.front();
                q.pop();
                if (top.first == n - 1 && top.second == n - 1)
                    break;
                for (int k = 0; k < 4; k++)
                {
                    int x = dx[k] + top.first;
                    int y = dy[k] + top.second;
                    if (x < 0 || x >= n || y < 0 || y >= n || d[x][y] < mid || vis[x][y] == mid)
                        continue;
                    vis[x][y] = mid;
                    q.push({ x, y });
                }
            }
            if (vis[n - 1][n - 1] == mid)
                left = mid;
            else right = mid - 1;
        }
        return left;
    }
};